package sword;

import java.util.LinkedList;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/22 20:16
 */
public class Title59II {

    /**
     * 单调队列
     */
    private LinkedList<Integer> queue;

    /**
     * 原始
     */
    private LinkedList<Integer> origin;

    public Title59II() {
        queue = new LinkedList<>();
        origin = new LinkedList<>();
    }

    public int max_value() {
        if (origin.isEmpty()) {
            return -1;
        }
        return queue.peek();
    }

    public void push_back(int value) {
        origin.offer(value);
        //维持单调队列
        while (!queue.isEmpty() && value > queue.getLast()) {
            queue.pollLast();
        }
        queue.offer(value);
    }

    public int pop_front() {
        if (origin.isEmpty()) {
            return -1;
        }
        int value = origin.poll();
        if (queue.peek() == value) {
            queue.poll();
        }
        return value;
    }

    public static void main(String[] args) {

    }
}
